Hard disks and flash memories both provide for non-volatile data storage. Due to the historical sequence of development of these devices, the protocols for managing the storage of data on hard disks were quite mature by the time that flash memory systems reached the marketplace. Interface protocols such as Small Computer Systems Interface (SCSI), Serial Advanced Technology Attachment (Serial ATA or SATA) and the like, took account of the properties of hard disks. These properties include, for example, a fixed sector or page size and a fixed relationship between a logical block address (LBA) and a particular sector on a disk. These relationships need not be exposed to the user. Magnetic disk media have the property that new data may be written to a sector even if there is data presently written to the sector. The new data replaces or “overwrites” the old data without any overt operation to erase the data in the sector being needed.
In contrast, NAND flash memory, which is often used for products that emulate hard disks, or for larger memory systems that are to be managed using legacy interface protocols, has different properties and characteristics. While a NAND flash memory circuit may be written in units of, for example, a page size, data that is to be written to the flash memory circuit needs to be written to a page that has no current data. To provide such pages, the pages need to be “erased” and erasing can only be done for a plurality of contiguous pages known as a block. There may be, for example, 64 or 128 such pages in a block.
The relationship between the user logical block address (LBA) and the actual physical location of the page of data in the flash memory is managed by series of algorithms that are vendor specific, but are intended to accomplish at least the functions of “garbage collection” and “wear leveling.” When data is written to an LBA, a particular physical block (memory page) address (PBA) is selected such that the data is written to a physical location that is mapped to the LBA by a table known as the logical-to-physical (L2P) table. This table may store other attributes of the LBA/PBA tuple as well. The Flash Translation Layer (FTL) typically organizes writes of new data to physical block addresses (PBAs) such that writes occur in sequentially ascending page order, or some order that is compatible with the specific flash circuit. The details of the writing operation may differ for single level cell (SLC), multiple level cell (MLC) and triple level cell (TLC) flash technologies, and similar details may differ as the technology evolves, such as stacked die and the like. The lower level details of the actual write operation are not typically of relevance to the user and are often hidden from the user. Since the logical block addresses (LBAs) may typically be written in any order to satisfy the needs of the using application or file management system, the relationship between the LBA and the PBA is complex.
A person of skill in the art would understand the difference between a block of flash memory, which may comprise a plurality of pages, grouped for management (e.g. erasure) purposes, a page of data having a logical block address (LBA), and the location of the page of data in the block of flash memory, the location having a physical block address (PBA) where the page of data referenced by the LBA is actually stored in the block of flash memory.
When the data being stored at a LBA is changed, the new (or updated) data for the LBA cannot be stored in the current PBA indicated in a logical-to-physical address (L2P) table, but needs to be stored in an unwritten (“free” or “erased”) physical memory location. The FTL performs the allocation of a new PBA for the data, taking account of the restrictions previously mentioned, and updates the L2P table so that the LBA points to the new PBA. After some time, it will be appreciated that there will not be any remaining unwritten pages and, prior to that time, some of the previously used memory needs to be reclaimed (“garbage collected”). The PBAs that held data that was replaced by new data and stored elsewhere are no longer current and are not accessible to the user as they are no longer linked with an LBA in the L2P table. These pages may be called, “stale”, “invalid” or the like. One would like to erase these pages; however, typically, the physical block in which the invalid pages reside still has some pages containing valid data that is referenced by the L2P table.
The garbage collection process may operate by moving the valid data pages of a block to PBAs in another block, and updating the L2P table accordingly. When all of the valid data has been moved, all of the PBAs of the block are now “invalid” and the block may be erased. This results in the reclaiming of physical memory locations that did not have useful data, so as to provide for an erased block of contiguous pages to continue the process of storing data.
File management systems developed for disk memory systems operate differently. For example, pages of data may be deleted from a file, or a file may be deleted, freeing the corresponding LBAs. The data that was recorded on the disk, but is no longer needed need not be erased from the disk as, when the physical page corresponding to a LBA is needed to write new data to the LBA, the new data is written to the physical page and directly overwrites the old (invalid) data. However, when such a file management system is managing a flash memory, and the flash memory is operated to emulate a disk, for example, there was no protocol for communicating the deletion of the LBAs to the flash page management software (FTL) as rendering the LBA and the associated PBA invalid. So, while the data in the LBAs, and the corresponding PBAs of the flash memory would no longer be needed or be accessible by the user, there was no indication of this situation at the L2P table interface with the FTL in a flash memory.
When the garbage collection process was executed on a block of pages of the flash memory, LBAs that may correspond to pages deleted by the file management system are still considered as having valid data in the PBA. Only when the user writes new data to the LBAs is the status of the PBA where the invalid data had been stored changed to “invalid”, so it can be garbage collected. The terms “old”, “stale,” or the like, may also be used to represent invalid data. That is, data no longer of use to the user.
This means that if a block that is being garbage collected contains PBAs mapped to LBAs that have been deleted by the user file system, the status of the LBAs would still be considered as valid by the FTL. As valid LBA/PBA entries in the L2P table, the data stored in the flash memory pages would be relocated along with all of the other valid data during a garbage collection operation. Since a user may have deleted a significant number of pages from a file, the lack of awareness of this situation at the flash memory management level causes the relocation of data that could otherwise be erased as being invalid. Since relocating data takes time and system bandwidth, and flash memory circuits are also subject to wear associated with writing data, this situation may be undesirable. There may be a considerable area of memory filled with data that is no longer referenced by the user, but cannot be freed in advance of the user writing to the previously associated LBA.
So as to mitigate this problem, the (S)ATA industry standard has been modified to introduce a command known as TRIM (nota bene, while this term is usually capitalized, it is not an acronym.) When a TRIM command for a LBA or LBA range is received by a flash memory system and the FTL is configurable to process such a command, the corresponding LBAs and PBAs may be marked as invalid, and the space reclaimed by erasure when a garbage collection operation is performed, rather than first moving the invalid data to a new physical memory location. Should the LBA be written to again prior to a garbage collection operation on the block containing the PBA, the FTL operates as usual by finding a unwritten page, writing the new data to a newly selected PBA, and updating the L2P table by marking the PBA that held the old data as being invalid.
The corresponding SCSI protocol provides an UNMAP command and WRITE SAME (10, 16) command with unmap flag to accomplish the same purpose as TRIM. Herein, for simplicity any of these commands will be termed TRIM. At present neither protocol addresses the subject of a Redundant Array of Independent (or Inexpensive) Disks (RAID), where the RAID comprises at least two separate storage devices storing data having redundant properties (e.g., parity). The description herein relates to both redundant and non-redundant data storage.